(2020) Semi-Fast Byzantine-tolerant Shared Register without Reliable Broadcast

2022-08-27 · 1 min read

properties #

  • BFT shared register w/o reliable broadcast
  • leaderless
  • unauthenticated: doesn't require digital signatures
  • no reconfiguration
  • one-shot read: read from at least f+1
  • two-RTT write: (1) do read from f+1, then (2) send store request to all servers.

core algorithm #

  • Store an (unauthenticated) tag version counter next to the register.
  • Client Writing:
    • (1) request current tag version from all servers
    • (2) determine the current honest tag $t$ to be the $(f + 1)$-th highest tag version.
      • remember that the register is unauthenticated, so byzantine servers can just return any tag version.
    • (3) send a store request with tag version $t + 1$
  • Client Reading:
    • (1) Request the current register state from all servers
    • (2) Return the value with the highest tag that was witnessed by at least $f + 1$ servers.

client # 

client-write(S: Servers, w: Writer, v: Value):
	1. try to get the current tag for the register, t := client-get-tag(S, w)
	2. try to update the register, client-put-data(S, w, t, v)

client-get-tag(S: Servers, w: Writer):
	1. send Query-Tag(w) message to servers in S
	2. wait for Query-Tag-Response(t, w) messages from (n - f) servers in S
	3. return t := (f + 1)-th highest tag among responses

client-put-data(S: Servers, w: Writer, t: Tag, v: Value):
	1. create new tag, t' := t + 1
	2. send Put-Data(w, t', v) to servers in S
	3. wait for ACKs from (n - f) servers in S

initial local client reader state:
	t_local := 0,
	v_local := v_0

client-read(S: Server, r: Reader, t: Tag):
	1. send Query-Data(r) to servers in S
	2. wait for Query-Data-Response(r, t, v) messages from (n - f) servers in S
	3. W := set of all (r, t, v) tuples with >= f + 1 witnesses
	4. select tuple (t, v) from witnesses W with highest tag
	5. if W != {} && t > t_local, then ratchet the local state tag
	6.     (t_local, v_local) := (t, v)
	7. return v_local

server # 

initial local server state (per reader/writer register):
	t_max := 0
	v_max := v_0

server(Query-Tag(w: Writer)):
	1. return Query-Tag-Response(t_max, w)

server(Put-Data(w: Writer, t: Tag, v: Value)):
	1. if t > t_max, then ratchet local register value and ACK:
	2.     t_max := t
	3.     v_max := v
	4.     send ACK response to w

server(Query-Data(r: Reader)):
	1. return Query-Data-Response(t_max, v_max) for Reader r